
// 一个数组 + 两次遍历
// 时间复杂度：O(n)
int candy(int* ratings, int ratingsSize) {
    int n = ratingsSize;
    int* left2right = (int*)malloc(sizeof(int) * n);

    for (int i = 0; i < n; i++) {
        left2right[i] = 1;
    }

    for (int i = 0; i < n; i++) {
        if (i != 0 && ratings[i] > ratings[i - 1]) {
            left2right[i] = left2right[i - 1] + 1;
        }
    }

    int sum = 0;
    int right = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (i != n - 1 && ratings[i] > ratings[i + 1]) {
            right++;
        } else {
            right = 1;
        }
        sum += fmax(left2right[i], right);
    }

    free(left2right);
    return sum;
}

// 两个数组 + 两次遍历
// 时间复杂度：O(n)
int candy2(int* ratings, int ratingsSize) {
     int n = ratingsSize;
    int* left2right = (int*)malloc(sizeof(int) * n);
    int* right2left = (int*)malloc(sizeof(int) * n);

    for (int i = 0; i < n; i++) {
        left2right[i] = 1;
        right2left[i] = 1;
    }

    for (int i = 0; i < n; i++) {
        if (i != 0 && ratings[i] > ratings[i - 1]) {
            left2right[i] = left2right[i - 1] + 1;
        }
    }

    int sum = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (i != n - 1 && ratings[i] > ratings[i + 1]) {
            right2left[i] = right2left[i + 1] + 1;
        }
        sum += fmax(left2right[i], right2left[i]);
    }
    free(left2right);
    free(right2left);
    return sum;
}

// 直接模拟，暴力解法，时间复杂度： O(n^2)，超时
int candy1(int* ratings, int ratingsSize) {
    int n = ratingsSize;

    int* candies = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        candies[i] = 1;
    }
    bool hasChanged = true;
    while (hasChanged) {
        hasChanged = false;
        for (int i = 0; i < n; i++) {
            if (i != n - 1 && ratings[i] > ratings[i + 1]
                    && candies[i] <= candies[i + 1]) {
                candies[i] = candies[i + 1] + 1;
                hasChanged = true;
            }
            if (i != 0 && ratings[i] > ratings[i - 1]
                    && candies[i] <= candies[i - 1]) {
                candies[i] = candies[i - 1] + 1;
                hasChanged = true;
            }
        }
    }

    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += candies[i];
    }
    free(candies);
    return sum;
}